/*
https://leetcode.cn/problems/burst-balloons/submissions/585716196/
312. 戳气球
*/
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size(); // 获取气球的数量
        vector<int> a(n + 2, 1); // 创建a数组为nums前后各加一个1
                          // 与题目超边界视为数字为1的气球要求对应
        for (int i = 0; i < n; i++) { 
            a[i + 1] = nums[i];// 将nums元素复制到a中
        }
        // dp[i][j]表示戳破a[i...j]的气球能够获得的最大硬币数。
        vector<vector<int>> dp(n + 2, vector<int>(n + 2));
        // 遍历子问题的长度，从3到n+2（+2是因为我们加了边界的1）
        for (int len = 3; len <= n + 2; len++) {
            for (int l = 0; l <= n + 2 - len; l++) {
                int r = l + len - 1;
                // 枚举在l和r之间戳破的气球
                for (int k = l + 1; k < r; k++) { // k:需要戳破的气球的下标
                    // 更新dp[l][r]，选择当前k气球的收益
                    dp[l][r] = max(dp[l][r],dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
                    // dp[l][k]表示戳破last之前的气球获得的硬币数量
                    // dp[k][r]表示戳破last之后的气球获得的硬币数量
                    // a[l] * a[k] * a[r]表示戳破last气球获得的硬币数量
                }
            }
        }
        return dp[0][n + 1]; //戳破所有气球能够获得的最大硬币数
    }
};